/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-ladder-ii
   @Language: C++
   @Datetime: 17-03-29 16:09
   */

class Solution {
	void dfs(unordered_map<string,unordered_set<string> > &trace, const string &last, vector<string> path, vector<vector<string> > &vs){
		path.push_back(last);
		if(trace.count(last)==0){
			reverse(path.begin(),path.end());
			vs.push_back(path);
			return;
		}
		for(const string &word:trace[last])
			dfs(trace,word,path,vs);
	}
public:
	/*
	 * @param start: a string
	 * @param end: a string
	 * @param dict: a set of string
	 * @return: a list of lists of string
	 */
	vector<vector<string>> findLadders(string &start, string &end, unordered_set<string> &dict) {
		// write your code here
		dict.insert(end);
		unordered_map<string,unordered_set<string> > trace;
		unordered_set<string> q={start}, dels;
		for(; q.size() && trace.count(end)==0; q=dels){
			for(const string &word:q)
				dict.erase(word);
			dels.clear();
			for(const string &word:q){
				for(int i=0; i<word.length(); ++i){
					string s=word;
					for(char ch='a'; ch<='z'; ++ch){
						if(word[i]==ch) continue;
						s[i] = ch;
						if(dict.find(s)==dict.end()) continue;
						trace[s].insert(word);
						dels.insert(s);
					}
				}
			}
		}
		if(trace.size()==0) return {};
		vector<vector<string> > result;
		dfs(trace,end,{},result);
		return result;
	}
};
